package leetcode.code1129;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

public class Solution {
	public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
		List<Set<Integer>> reds = new ArrayList<>();
		List<Set<Integer>> blues = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			reds.add(new HashSet<>());
			blues.add(new HashSet<>());
		}
		for (int i = 0; i < redEdges.length; i++) {
			int[] r = redEdges[i];
			reds.get(r[0]).add(r[1]);
		}
		for (int i = 0; i < blueEdges.length; i++) {
			int[] r = blueEdges[i];
			blues.get(r[0]).add(r[1]);
		}
		int ans[] = new int[n];
		boolean redhere[] = new boolean[n];
		boolean bluehere[] = new boolean[n];
		Arrays.fill(ans, -1);
		ans[0] = 0;
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { -1, 0, 0 });// 0red,1blue,step
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int from = cur[0], index = cur[1], step = cur[2] + 1;
			if (from == 0 || from == -1) {// 曾经以红色抵达index
				Set<Integer> set = blues.get(index);
				for (int b : set) {
					if (!bluehere[b]) {
						bluehere[b] = true;
						if (ans[b] == -1) {
							ans[b] = step;
						}
						queue.add(new int[] { 1, b, step });
					}
				}
			}
			if (from == 1 || from == -1) {// 曾经以蓝色抵达index
				Set<Integer> set = reds.get(index);
				for (int b : set) {
					if (!redhere[b]) {
						redhere[b] = true;
						if (ans[b] == -1) {
							ans[b] = step;
						}
						queue.add(new int[] { 0, b, step });
					}
				}
			}
		}
		return ans;
	}

}
